#pragma once
#ifndef BABY_STEP_GIANT_STEP

#define BABY_STEP_GIANT_STEP

#include "../Lab1_Large_numbers/__uintX2.h"
#include <math.h>
#include <algorithm>
#include <map>

using namespace std;

typedef uint128 large_uint;
typedef map<large_uint, large_uint> table;

static large_uint get_discrete_log(const large_uint& a,
							       const large_uint& g,
							       const large_uint& mod)
{
	//uint64 m = (uint64) ceil(sqrtl((long double) mod));
	large_uint m = large_uint::one()<<((mod.size() + 1) / 2); // m = 2 ^ (size/2) >= mod ^ (1/2)

	m = 28;
	table baby_set;
	large_uint b = large_uint::pow_m(g, m, mod);

	for(large_uint i = 1; i <= m; ++i)
	{
		//large_uint baby = large_uint::pow_m(b, i, mod);
		large_uint baby = large_uint::mult_m(a, large_uint::pow_m(g, i, mod), mod);
		baby_set.insert(pair<large_uint, large_uint>(baby,i));
#ifdef SCREEN_LOG
		cout<<i._l<<": "<<baby<<"\n";
#endif /* SCREEN LOG */
	}
#ifdef SCREEN_LOG
	cout<<"\nbaby generated.comparing..\n\n";
#endif /* SCREEN LOG */

	for(large_uint i = 1; i <= m; ++i)
	{
		//large_uint giant = large_uint::mult_m(a, large_uint::pow_m(g, i, mod), mod);
		large_uint giant = large_uint::pow_m(b, i, mod);
#ifdef SCREEN_LOG
		cout<<i._l<<": find "<<giant<<" in baby array\n";
#endif /* SCREEN LOG */
		table::iterator found = baby_set.lower_bound(giant);
		if(found!=baby_set.end() && (found->first == giant)) 
		{
			//return (m * i - found->second) % mod; 
#ifdef SCREEN_LOG
			cout<<"\n\nLog is found\n";
			cout<<"Log = ((m = "<<m<<" * giant index = "<<i<<") - baby index = "<<found->second<<")"<<endl;
#endif /* SCREEN LOG */
			//return uint128::sub_m(uint128::mult_m(m, found->second, mod), i, mod);
			return uint128::sub_m(uint128::mult_m(m, i, mod), found->second, mod);
		}
	}
	return 0;
}
#endif /* BABY_STEP_GIANT_STEP */
